1. Field of the Invention
The invention relates to a method for calculating syndromes in Reed-Solomon decoding, more particularly to a method for efficiently calculating syndromes in Reed-Solomon decoding using a finite field vector multiplication table, and to a machine-readable storage medium storing a plurality of instructions for executing the method.
2. Description of the Related Art
In recent years, demand for reliable signal transmission with respect to products ranging from consumer electronic products to communications electronic products has increased considerably. Therefore, error detection and correction mechanisms are becoming more and more important. During the process of digital communication, to ensure the accuracy of source data to be transmitted, a transmitting end generally will append redundant data to the source data, so that the receiving end can perform error correction based on the redundant data. The Reed-Solomon code is a widely used correction code. Since the Reed-Solomon code has a good correction capability with respect to errors generated in transmission channels, it has become a very popular channel coding scheme, and is now a widely used error correction code in satellite communication systems, digital television systems, various digital audiovisual recording media, etc.
Even though the Reed-Solomon code has excellent performance in error correction, the amount of computations required for decoding is huge. Consequently, hardware is often used for calculation and processing. If the Reed-Solomon code is executed in a processor in the form of program decoding, the decoding speed will inevitably become extremely slow due to the huge computation amount. Therefore, in some applications of communications devices with software-defined operations (such as software defined radio (SDR), accelerating the program decoding speed of the Reed-Solomon code has become an important subject of research.
Referring to FIG. 1, a current optimized Reed-Solomon decoding procedure can be divided into three major stages, which are, as shown, a stage 11 of calculating syndromes, a stage 12 of finding error positions, and a stage 13 of evaluating error values. During the Reed-Solomon decoding process, about 60% of the computation amount is concentrated on the calculation of syndromes at stage 11. If the processing time for calculating syndromes at stage 11 can be effectively reduced, the decoding speed of the Reed-Solomon code can be successfully accelerated.
Referring to FIG. 2, a first scheme used to calculate syndromes in conventional Reed-Solomon decoding is to reduce the time for calculating Galois field multiplications using look-up tables so as to accelerate the overall speed of syndrome calculations. This scheme includes the following steps. In step 201, outer and inner loop indices are initialized, i=0, and j=1. In step 202, αi is acquired from a memory, and β is caused to be equal to αi, where α is a selected primitive element of the Galois field. In step 203, an input byte R(0) is received, and initialization is performed so that Si=R[0]. In step 204, the result of the Galois field multiplication Si×β is found by first looking up a GF_LOG table to find the corresponding logarithmic values of Si and β, i.e., GF_LOG[Si] and GF_LOG[β]. Subsequently, a Galois field modulo (P−1) addition is performed to find a logarithmic sum: LOGSUM=(GF_LOG [Si]+GF_LOG[β])MOD(P−1). Finally, a GF_EXP table is looked up to find GF_EXP[LOGSUM]. Thus, the required Galois field multiplication result is GF_EXP[LOGSUM]. In step 205, a Galois field addition of the Galois field multiplication result GF_EXP[LOGSUM] and the input byte R(j) is performed, and the result is stored as the current value of Si. In steps 206 to 210, it is determined whether the syndrome calculation has been completed. If affirmative, the syndrome calculation is ended. Otherwise, the aforesaid steps are repeated.
Referring to FIG. 3, a second scheme used to calculate syndromes in conventional Reed-Solomon decoding is disclosed in U.S. Pat. No. 6,263,470, which uses another table look-up method to reduce the time for calculating Galois field multiplications so as to accelerate the overall speed of syndrome calculations. For the sake of brevity, a description of the steps of the second scheme which are similar to those of the first scheme is omitted herein, and only the difference between the table look-up steps 204 (see FIG. 2) and 303 in the first and second schemes will be discussed herein. In step 303 of the second scheme, according to outer and inner loop indices i, j, the Galois field multiplication result is directly looked up from a pre-defined multiplication result table.
The GF_LOG table and the GF_EXP table used in the aforesaid first scheme do not require a lot of space (e.g., for GF(256), 256 bytes are required for each table), and can be stored in an internal memory which is relatively costly and which permits access at a relatively fast speed. However, obtaining the result of the Galois field multiplication at least requires looking up the GF_LOG table twice, one Galois field addition, and looking up the GF_EXP table once for each operation. The Galois field multiplication result cannot be directly obtained by looking up a table.
The aforesaid second scheme permits finding the Galois field multiplication result directly from the pre-defined multiplication result table. However, the pre-defined multiplication result table requires a larger space (e.g., for GF(256), 4K bytes are required), and is generally stored in an external memory which is comparatively inexpensive and which permits access at a relatively low speed. As a result, the time required to read one entry of data may even be longer than the time required to do one Galois field multiplication in the first scheme.
Therefore, there is a need for a solution, so that a Galois field multiplication result can be directly obtained by looking up a table in the calculation of syndromes while reducing the average time needed to read each entry of data, so as to accelerate the decoding speed of the Reed-Solomon code.